/*
 * File: dlist.c
 * Author:  Yin Lijun <yinlijun2004@gmail.com>
 * Brief:   dlist interface.
 *
 * Copyright (c) 2011 - 2012  Yin Lijun <yinlijun2004@gmail.com>
 *
 * Licensed under the Academic Free License version 2.1
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/*
 * History:
 * ================================================================
 * 2012-03-12 Yin Lijun <yinlijun2004@gmail.com> created
 *
 * 2013-11-25 Yin Lijun <yinlijun2004@gmail.com> add dlist_find_by_data interface
 */
#include "dlist.h"

typedef struct _DListNode {
	struct _DListNode* prev;
	struct _DListNode* next;
	void* data;
}DListNode;

struct _DList {
	size_t length;
	DListNode* head;
	DestoryFunc dest_func;
};

static DListNode* dlist_create_node(void* data)
{
	DListNode* node = (DListNode *)malloc(sizeof(DListNode));
	return_if_fail_val(node != NULL, NULL);
	node->prev = NULL;
	node->next = NULL;
	node->data = data;

	return node;
}

static DListNode* dlist_find_node(DList* thiz, size_t index)
{
	DListNode* iter = thiz->head;
	while(iter != NULL && index > 0)
	{
		index--;
		iter = iter->next;
	}

	return iter;
}

DList* dlist_create(DestoryFunc dest_func)
{
	DList* thiz = (DList *)malloc(sizeof(DList));
	return_if_fail_val(thiz != NULL, NULL);
	
	thiz->dest_func = dest_func;
	thiz->length = 0;
	thiz->head = NULL;

	return thiz;
}

Ret dlist_prepend(DList* thiz, void* data)
{
	return dlist_insert(thiz, data, 0);	
}

Ret dlist_append(DList* thiz, void* data)
{
	return dlist_insert(thiz, data, thiz->length);
}

Ret dlist_insert(DList* thiz, void* data, size_t before_index)
{
	return_if_fail_val(thiz != NULL
					&& before_index <= thiz->length,
					RET_PARAM_ERROR);
	DListNode* inserting = dlist_create_node(data);
	return_if_fail_val(inserting != NULL, RET_OVERFLOW);
	DListNode* prev_node = dlist_find_node(thiz, before_index - 1);
	DListNode* next_node = dlist_find_node(thiz, before_index);
	
	if(prev_node == NULL && next_node == NULL)
	{
		//no nodes, insert as head
		thiz->head = inserting;
		thiz->length++;

		return RET_OK;
	}
	
	if(prev_node != NULL)
	{
		prev_node->next = inserting;
		inserting->prev = prev_node;
	} 
	else 
	{
		//insert before head
		thiz->head = inserting;
	}

	if(next_node != NULL)
	{
		next_node->prev = inserting;
		inserting->next = next_node;
	}

	thiz->length++;
	
	return RET_OK;
}

void* dlist_find_by_data(DList* thiz, void* data, CompareFunc cmp_func, int* index)
{
    return_if_fail_val(thiz != NULL
                && data != NULL
                && cmp_func != NULL, NULL);
    
    DListNode* iter = thiz->head;
    int idx = -1;
	while(iter != NULL)
	{
        idx++;
        if(!cmp_func(data, iter->data))
        {
            break;
        }
		iter = iter->next;
	}
    if(index != NULL)
    {
        *index = idx;
    }
	return iter == NULL ? NULL : iter->data;

}

Ret dlist_get_data_by_index(DList* thiz, size_t index, void** data)
{
	return_if_fail_val(thiz != NULL 
					&& index < thiz->length
					&& data != NULL,
					RET_PARAM_ERROR);
	DListNode* getting = dlist_find_node(thiz, index);
	*data = getting->data;

	return RET_OK;
}

Ret dlist_delete(DList* thiz, size_t index)
{
	return_if_fail_val(thiz != NULL 
					&& index < thiz->length,
					RET_PARAM_ERROR);
	DListNode* deleting = dlist_find_node(thiz, index);
	DListNode* prev_node = deleting->prev;
	DListNode* next_node = deleting->next;
	if(prev_node != NULL)
	{
		prev_node->next = next_node;
	}
	else
	{
		// deleting the head, take next_node as new head
		thiz->head = next_node;
	}

	if(next_node != NULL)
	{
		next_node->prev = prev_node;
	}
    thiz->dest_func(deleting->data);
	free(deleting);
	thiz->length--;

	return RET_OK;
}

size_t dlist_get_length(DList* thiz)
{
	return_if_fail_val(thiz != NULL, 0);

	return thiz->length;
}

Ret dlist_foreach(DList* thiz, VisitFunc visit, void *ctx)
{
	return_if_fail_val(thiz != NULL
					&& visit != NULL, 
					RET_PARAM_ERROR);
	DListNode* iter = thiz->head;
	while(iter != NULL)
	{
		visit(ctx, iter->data);
		iter = iter->next;
	}

	return RET_OK;
}

Ret dlist_destroy(DList* thiz)
{
	return_if_fail_val(thiz != NULL, RET_PARAM_ERROR);
	DListNode* iter = thiz->head;
	if(thiz->dest_func != NULL) 
	{
		while(iter != NULL)
		{
			thiz->dest_func(iter->data);
			DListNode* temp = iter->next;
			free(iter);
			iter = temp;
		}
	}

	free(thiz);

	return RET_OK;
}

#ifdef __DLIST_TEST__
#include <stdio.h>
#include <assert.h>
#define TEST_SIZE 1000
void int_visit(void* ctx, void* data)
{
	printf("%4d", (int)data);
}

int main(int argc, char** argv)
{
	DList* dlist = dlist_create(NULL);
	assert(dlist != NULL);
	printf("\ntest dlist_prepend\n");
	size_t length = 0;
	int i = 0;
	int j = 0;
	for(; i < TEST_SIZE; i++)
	{
		assert(dlist_prepend(dlist, (void *)i) == RET_OK);
		assert(dlist_get_length(dlist) == ++length);
	   	assert(dlist_get_data_by_index(dlist, 0, (void **)&j) == RET_OK);
		assert(j == i);
	}
	assert(dlist_foreach(dlist, int_visit, NULL) == RET_OK);
	
	printf("\ntest dlist_append\n");
	for(--i; i >= 0; i--)
	{
		assert(dlist_append(dlist, (void *)i) == RET_OK);
		assert(dlist_get_length(dlist) == ++length);
		assert(dlist_get_data_by_index(dlist, dlist_get_length(dlist) - 1, (void **)&j) == RET_OK);
		assert(j == i);	
	}
	assert(dlist_foreach(dlist, int_visit, NULL) == RET_OK);

	printf("\ntest dlist_insert\n");
	for(i = 0; i < TEST_SIZE; i++)
	{
		assert(dlist_insert(dlist, (void *)i, TEST_SIZE) == RET_OK);
		assert(dlist_get_length(dlist) == ++length);
		assert(dlist_get_data_by_index(dlist, TEST_SIZE, (void **)&j) == RET_OK);
		assert(j == i);
	}
	assert(dlist_foreach(dlist, int_visit, NULL) == RET_OK);

	printf("\ntest dlist_delete\n");
	for(i = 0; i < TEST_SIZE; i ++)
	{
		assert(dlist_delete(dlist, TEST_SIZE) == RET_OK);
		assert(dlist_get_length(dlist) == --length);
	}
	assert(dlist_foreach(dlist, int_visit, NULL) == RET_OK);

	printf("\ntest dlist_delete\n");
	for(i = 0; i < TEST_SIZE; i ++)
	{
		assert(dlist_delete(dlist, 0) == RET_OK);
		assert(dlist_get_length(dlist) == --length);
	}
	assert(dlist_foreach(dlist, int_visit, NULL) == RET_OK);

	printf("\ntest dlist_destroy\n");
	assert(dlist_destroy(dlist) == RET_OK);

	return 0;
}
#endif
